package j20251016;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    StringBuilder path;
    List<String> ret;
    String[] change={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        path=new StringBuilder();
        ret=new ArrayList<>();
        dfs(digits,0);
        return ret;
    }
    public void dfs(String d,int pos){
        if(pos==d.length()){
            ret.add(path.toString());
            return;
        }
        String cur=change[d.charAt(pos)-'0'];
        for(int i=0;i<cur.length();i++){
            path.append(cur.charAt(i));
            dfs(d,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }

    StringBuilder path1;
    List<String> ret1;
    public List<String> generateParenthesis(int n) {
        path1=new StringBuilder();
        ret1=new ArrayList<>();
        dfs(0,0,n);
        return ret1;
    }
    public void dfs(int l,int r,int n){
        if(r==n){
            ret1.add(path1.toString());
            return;
        }
        if(l<n){
            path.append('(');
            dfs(l+1,r,n);
            path.deleteCharAt(path.length()-1);
        }
        if(r<l){
            path.append(')');
            dfs(l,r+1,n);
            path.deleteCharAt(path.length()-1);
        }
    }

    List<List<Integer>> ret2;
    List<Integer> path2;
    public List<List<Integer>> combine(int n, int k) {
        ret2=new ArrayList<>();
        path2=new ArrayList<>();
        dfs1(n,k,1);
        return ret2;
    }
    public void dfs1(int n,int k,int pos){
        if(path2.size()==k){
            ret2.add(new ArrayList<>(path2));
            return;
        }
        for(int i=pos;i<=n;i++){
            path2.add(i);
            dfs1(n,k,i+1);
            path2.remove(path2.size()-1);
        }
    }

    int count,sum;
    public int findTargetSumWays(int[] nums, int target) {
        dfs2(nums,target,0);
        return count;
    }
    public void dfs2(int[] nums,int t,int pos){
        if(pos==nums.length){
            if(sum==t){
                count++;
            }
            return;
        }
        if(pos<nums.length){
            sum+=nums[pos];
            dfs2(nums,t,pos+1);
            sum-=nums[pos];
        }
        if(pos<nums.length){
            sum-=nums[pos];
            dfs2(nums,t,pos+1);
            sum+=nums[pos];
        }
    }
}
